home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _spanning.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  1.1 KB  |  46 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _spanning.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  SPANNING_TREE  (spanning tree)                                              *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24. #include <LEDA/graph_alg.h>
  25. #include <LEDA/node_partition.h>
  26.  
  27.  
  28. list<edge> SPANNING_TREE(const graph& G)
  29. { node v,w;
  30.   edge e;
  31.   list<edge> EL;
  32.   node_partition P(G);
  33.  
  34.   forall_edges(e,G)
  35.      { v = source(e);
  36.        w = target(e);
  37.        if (! P.same_block(v,w))
  38.         { EL.append(e);
  39.           P.union_blocks(v,w);
  40.          }
  41.       }
  42.  
  43.   return EL;
  44. }
  45.  
  46.